package vg.services.graph_view_manager.realization.graph_comparison.algorithm;

import java.math.BigDecimal;
import java.util.*;
import java.util.concurrent.atomic.AtomicBoolean;

import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
import vg.interfaces.ll_services.data_base_service.data.graph.Attribute;
import vg.interfaces.ll_services.data_base_service.data.graph.AttributeItem;
import vg.interfaces.ll_services.data_base_service.data.graph.Edge;
import vg.interfaces.ll_services.data_base_service.data.graph.Graph;
import vg.interfaces.ll_services.data_base_service.data.graph.Vertex;
import vg.interfaces.ll_services.data_base_service.data.header.AttributeHeader;
import vg.services.graph_view_manager.interfaces.graph_comparison.IGraphComparisonAlgorithmObserver;
import vg.services.graph_view_manager.interfaces.graph_comparison.InputGraphComparisonAlgorithmProperties;
import vg.services.graph_view_manager.interfaces.graph_comparison.OutputGraphComparisonAlgorithmProperties;
import vg.services.graph_view_manager.realization.graph_comparison.algorithm.hungarian_algorithm.HungarianAlgorithm;
import vg.services.graph_view_manager.realization.graph_comparison.algorithm.hungarian_algorithm.HungarianAlgorithmOutput;
import vg.services.main_manager.VGMainServiceHelper;
import vg.shared.graph.utils.GraphUtils;

/**
 * Algorithm which compares two graphs.
 *
 * @author Timur Zolotuhin (e-mail: tzolotuhin@gmail.com)
 */
public class GraphComparisonAlgorithm {
	// Defines
	private static final String OUTGOING_COUNT_EDGE = "count of outgoing edges";
	private static final String INCOMING_COUNT_EDGE = "count of incoming edges";
	
	private static final float MAX_PERCENT_VALUE = 1.0f;
	private static final float MIN_PERCENT_VALUE = 0.0f;
    private static final float MIDDLE_PERCENT_VALUE = 0.75f;
	
	// Main data
	private Graph g1, g2;

    private float vertexBarrier;
    private float edgeBarrier;

    private boolean enableHeuristic;
    private boolean enableStrongComparison;

    public BiMap<Vertex, Vertex> unitedVertices;
    public BiMap<Vertex, Vertex> separatedVertices;

    private BiMap<Vertex, Vertex> outputGraphVertices2firstOriginalGraphVertices;
    private BiMap<Vertex, Vertex> outputGraphVertices2secondOriginalGraphVertices;

    private Map<String, Float> vertexAttribute2Weight = new HashMap<String, Float>();
    private Map<String, Float> edgeAttribute2Weight = new HashMap<String, Float>();

    private Map<String, Float> vertexAttribute2WeightRatio = new HashMap<String, Float>();
    private Map<String, Float> edgeAttribute2WeightRatio = new HashMap<String, Float>();

    private float[][] vertexMatchingTable;
    private float[][] edgeMatchingTable;

    private float[][] heuristicVertexMatchingTable;
    private float[][] heuristicEdgeMatchingTable;

    private AttributeItem[] g1Vertices, g2Vertices;
    private AttributeItem[] g1Edges, g2Edges;

    private BiMap<Vertex, Integer> firstGraphVertex2Index;
    private BiMap<Vertex, Integer> secondGraphVertex2Index;

    private BiMap<Edge, Integer> firstGraphEdge2Index;
    private BiMap<Edge, Integer> secondGraphEdge2Index;

    private AtomicBoolean stopAnyPhase = new AtomicBoolean(false);

    // Result data
    private Graph maximalCommonSubgraph;

    private List<Vertex> g1OtherVertices;
    private List<Vertex> g2OtherVertices;

    private List<Edge> g1OtherEdges;
    private List<Edge> g2OtherEdges;

    /**
     * Initialize graph comparison algorithm using input graphs.
     * @exception IllegalArgumentException
     *                                  if g1 or g2 is <b>null</b>.
     */
    public GraphComparisonAlgorithm(Graph g1, Graph g2) {
		if (g1 == null || g2 == null)
            throw new IllegalArgumentException("g1 == null || g2 == null");

        this.g1 = g1;
		this.g2 = g2;

		init();
	}
	
//=============================================================================	
//-----------------Public methods----------------------------------------------
    public void execute(IGraphComparisonAlgorithmObserver observer) {
        stopAnyPhase.set(false);

        try {
            observer.startProcess();

            // run phases
            runPhase1(observer);
            Solution solution = runPhase2(observer);
            maximalCommonSubgraph = runPhase3(solution, observer);

            observer.finishProcess();
        } catch (Throwable ex) {
            VGMainServiceHelper.logger.printException(ex);
        }
    }

    public void stopAnyPhase() {
        stopAnyPhase.set(true);
    }

    public void setInputGraphComparisonAlgorithmProperties(InputGraphComparisonAlgorithmProperties input) {
        vertexBarrier = input.getVertexBarrier();
        edgeBarrier = input.getEdgeBarrier();

        vertexAttribute2Weight = input.getVertexAttributeAndWeightTable();
        edgeAttribute2Weight = input.getEdgeAttributeAndWeightTable();

        enableHeuristic = input.isEnableHeuristic();
        enableStrongComparison = input.isEnableStrongComparison();

        unitedVertices = input.getUnitedVertices();
        separatedVertices = input.getSeparatedVertices();

        calculateWeightRatio();
    }

    public InputGraphComparisonAlgorithmProperties getInputGraphComparisonAlgorithmProperties() {
        InputGraphComparisonAlgorithmProperties input = new InputGraphComparisonAlgorithmProperties();

        input.setVertexBarrier(vertexBarrier);
        input.setEdgeBarrier(edgeBarrier);

        input.setEnableHeuristic(enableHeuristic);
        input.setEnableStrongComparison(enableStrongComparison);

        input.setVertexAttributeAndWeightTable(vertexAttribute2Weight);
        input.setEdgeAttributeAndWeightTable(edgeAttribute2Weight);

        input.setUnitedVertices(unitedVertices);
        input.setSeparatedVertices(separatedVertices);

        return input;
    }

    public OutputGraphComparisonAlgorithmProperties getOutputGraphComparisonAlgorithmProperties() {
        OutputGraphComparisonAlgorithmProperties output = new OutputGraphComparisonAlgorithmProperties();

        // save value of barriers
        output.setVertexBarrier(vertexBarrier);
        output.setEdgeBarrier(edgeBarrier);

        // save input graphs
        output.setFirstGraph(g1);
        output.setSecondGraph(g2);

        // save result
        output.setMaximalCommonSubgraph(maximalCommonSubgraph);
        output.setFirstGraphVertexOutsiders(g1OtherVertices);
        output.setSecondGraphVertexOutsiders(g2OtherVertices);
        output.setFirstGraphEdgeOutsiders(g1OtherEdges);
        output.setSecondGraphEdgeOutsiders(g2OtherEdges);

        // save other data
        output.setVertexAttributeAndWeightTable(vertexAttribute2Weight);
        output.setEdgeAttributeAndWeightTable(edgeAttribute2Weight);

        output.setVertexMatchingTable(vertexMatchingTable);
        output.setEdgeMatchingTable(edgeMatchingTable);
        output.setHeuristicVertexMatchingTable(heuristicVertexMatchingTable);
        output.setHeuristicEdgeMatchingTable(heuristicEdgeMatchingTable);

        output.setOutputGraphVertices2firstOriginalGraphVertices(outputGraphVertices2firstOriginalGraphVertices);
        output.setOutputGraphVertices2secondOriginalGraphVertices(outputGraphVertices2secondOriginalGraphVertices);

        return output;
    }

    public OutputGraphComparisonAlgorithmProperties estimate(InputGraphComparisonAlgorithmProperties input) {
        OutputGraphComparisonAlgorithmProperties output = new OutputGraphComparisonAlgorithmProperties();

        output.setVertexBarrier(input.getVertexBarrier());
        output.setEdgeBarrier(input.getEdgeBarrier());

        output.setVertexMatchingTable(buildVertexMatchingTable());
        output.setEdgeMatchingTable(buildEdgeMatchingTable());

        SolutionSet solutionSet = new SolutionSet(output.getVertexMatchingTable(), output.getVertexBarrier());
        output.setUpperBoundCountCases(solutionSet.upperBoundCountCases());

        // apply united and separated vertex lists
        if (input.getUnitedVertices() != null && input.getUnitedVertices().size() > 0) {
            for (Vertex src : input.getUnitedVertices().keySet()) {
                Vertex trg = input.getUnitedVertices().get(src);

                Integer re = firstGraphVertex2Index.get(src);
                if (re == null)
                    continue;
                int idx1 = re;

                re = secondGraphVertex2Index.get(trg);
                if (re == null)
                    continue;
                int idx2 = re;

                for (int i = 0; i < g1.getVertexCount(); i++) {
                    output.getVertexMatchingTable()[i][idx2] = MIN_PERCENT_VALUE;
                }

                for (int i = 0; i < g2.getVertexCount(); i++) {
                    output.getVertexMatchingTable()[idx1][i] = MIN_PERCENT_VALUE;
                }

                output.getVertexMatchingTable()[idx1][idx2] = MAX_PERCENT_VALUE;
            }
        }

        if (input.getSeparatedVertices() != null && input.getSeparatedVertices().size() > 0) {
            for (Vertex src : input.getSeparatedVertices().keySet()) {
                Vertex trg = input.getSeparatedVertices().get(src);

                Integer re = firstGraphVertex2Index.get(src);
                if (re == null)
                    continue;
                int idx1 = re;

                re = secondGraphVertex2Index.get(trg);
                if (re == null)
                    continue;
                int idx2 = re;

                output.getVertexMatchingTable()[idx1][idx2] = MIN_PERCENT_VALUE;
            }
        }

        // Hungarian optimization
        float[][] cost = new float[g1.getVertexCount()][g2.getVertexCount()];
        float[][] vertexMatchingTableHungarianOptimization = new float[g1.getVertexCount()][g2.getVertexCount()];

        HungarianAlgorithmOutput hungarianAlgorithmOutput = new HungarianAlgorithm(output.getVertexMatchingTable(), HungarianAlgorithm.MAXIMIZE).execute();
        if (hungarianAlgorithmOutput != null) {
            cost = hungarianAlgorithmOutput.getCost();
        }

        for (int i = 0; i < cost.length; i++) {
            for (int j = 0; j < cost[i].length; j++) {
                if (cost[i][j] == 0 && output.getVertexMatchingTable()[i][j] >= input.getVertexBarrier()) {
                    vertexMatchingTableHungarianOptimization[i][j] = output.getVertexMatchingTable()[i][j];
                } else {
                    vertexMatchingTableHungarianOptimization[i][j] = 0;
                }
            }
        }

        output.setHeuristicVertexMatchingTable(vertexMatchingTableHungarianOptimization);
        output.setHeuristicEdgeMatchingTable(output.getEdgeMatchingTable());

        SolutionSet hungarianSolutionSet = new SolutionSet(vertexMatchingTableHungarianOptimization, output.getVertexBarrier());
        output.setUpperBoundHeuristicCountCases(hungarianSolutionSet.upperBoundCountCases());

        return output;
    }

//==============================================================================
//-----------------PRIVATE METHODS----------------------------------------------
    /**
     * Builds vertex & edge math tables.
     */
    private void runPhase1(IGraphComparisonAlgorithmObserver observer) {
        vertexMatchingTable = buildVertexMatchingTable();
        edgeMatchingTable = buildEdgeMatchingTable();

        // apply united and separated vertex lists
        if (unitedVertices != null && unitedVertices.size() > 0) {
            for (Vertex src : unitedVertices.keySet()) {
                Vertex trg = unitedVertices.get(src);

                Integer re = firstGraphVertex2Index.get(src);
                if (re == null)
                    continue;
                int idx1 = re;

                re = secondGraphVertex2Index.get(trg);
                if (re == null)
                    continue;
                int idx2 = re;

                for (int i = 0; i < g1.getVertexCount(); i++) {
                    vertexMatchingTable[i][idx2] = MIN_PERCENT_VALUE;
                }

                for (int i = 0; i < g2.getVertexCount(); i++) {
                    vertexMatchingTable[idx1][i] = MIN_PERCENT_VALUE;
                }

                vertexMatchingTable[idx1][idx2] = MAX_PERCENT_VALUE;
            }
        }

        if (separatedVertices != null && separatedVertices.size() > 0) {
            for (Vertex src : separatedVertices.keySet()) {
                Vertex trg = separatedVertices.get(src);

                Integer re = firstGraphVertex2Index.get(src);
                if (re == null)
                    continue;
                int idx1 = re;

                re = secondGraphVertex2Index.get(trg);
                if (re == null)
                    continue;
                int idx2 = re;

                vertexMatchingTable[idx1][idx2] = MIN_PERCENT_VALUE;
            }
        }

        // Hungarian optimization
        if (enableHeuristic) {
            float[][] cost = new float[g1.getVertexCount()][g2.getVertexCount()];
            heuristicVertexMatchingTable = new float[g1.getVertexCount()][g2.getVertexCount()];
            heuristicEdgeMatchingTable = new float[g1.getEdgeCount()][g2.getEdgeCount()];

            HungarianAlgorithmOutput hungarianAlgorithmOutput = new HungarianAlgorithm(vertexMatchingTable, HungarianAlgorithm.MAXIMIZE).execute();
            if (hungarianAlgorithmOutput != null) {
                cost = hungarianAlgorithmOutput.getCost();
            }

            for (int i = 0; i < cost.length; i++) {
                for (int j = 0; j < cost[i].length; j++) {
                    if (cost[i][j] == 0 && vertexMatchingTable[i][j] >= vertexBarrier) {
                        heuristicVertexMatchingTable[i][j] = vertexMatchingTable[i][j];
                    } else {
                        heuristicVertexMatchingTable[i][j] = 0;
                    }
                }
            }

            for (int i = 0; i < g1.getEdgeCount(); i++) {
                for (int j = 0; j < g2.getEdgeCount(); j++) {
                    heuristicEdgeMatchingTable[i][j] = edgeMatchingTable[i][j];
                }
            }
        }
    }

    /**
     * Matching.
     */
    private Solution runPhase2(IGraphComparisonAlgorithmObserver observer) {
        if (enableHeuristic)
            return matching(new SolutionSet(heuristicVertexMatchingTable, vertexBarrier), observer);
        else
            return matching(new SolutionSet(vertexMatchingTable, vertexBarrier), observer);
    }

    /**
     * Builds maximal common subgraph.
     */
    private Graph runPhase3(Solution solution, IGraphComparisonAlgorithmObserver observer) {
        return buildMaximalCommonSubgraph(solution);
    }

    // Build maximal common subgraph
	private Graph buildMaximalCommonSubgraph(Solution solution) {
        // initialize output data
        outputGraphVertices2firstOriginalGraphVertices = HashBiMap.create();
        outputGraphVertices2secondOriginalGraphVertices = HashBiMap.create();

		BiGraphEdge[] edges = solution.getEdges();

		// build general vertices
        Vertex[][] newVertexMergeTable = new Vertex[g1.getVertexCount()][g2.getVertexCount()];
        Map<Integer, Vertex> newG1VertexMergeMap = new HashMap<Integer, Vertex>();
        Map<Integer, Vertex> newG2VertexMergeMap = new HashMap<Integer, Vertex>();

        Set<Integer> g1GeneralIdxSet = new HashSet<Integer>();
        Set<Integer> g2GeneralIdxSet = new HashSet<Integer>();
        List<Vertex> newGeneralVertices = new ArrayList<Vertex>();
        for (BiGraphEdge edge : edges) {
            int idx1 = edge.getSrc();
            int idx2 = edge.getDst();

            g1GeneralIdxSet.add(idx1);
            g2GeneralIdxSet.add(idx2);

            Vertex v1 = firstGraphVertex2Index.inverse().get(idx1);
            Vertex v2 = secondGraphVertex2Index.inverse().get(idx2);

            Vertex v = new Vertex(mergingAttributeItems(v1, v2));
            newVertexMergeTable[idx1][idx2] = v;
            newG1VertexMergeMap.put(idx1, v);
            newG2VertexMergeMap.put(idx2, v);
            newGeneralVertices.add(v);

            outputGraphVertices2firstOriginalGraphVertices.put(v, v1);
            outputGraphVertices2secondOriginalGraphVertices.put(v, v2);
        }

        // build other vertices for g1
        g1OtherVertices = new ArrayList<Vertex>();
        for (Integer idx : firstGraphVertex2Index.inverse().keySet()) {
            if (!g1GeneralIdxSet.contains(idx)) {
                Vertex v = firstGraphVertex2Index.inverse().get(idx);
                g1OtherVertices.add(v);
                outputGraphVertices2firstOriginalGraphVertices.put(v, v);
            }
        }

        // build other vertices for g2
        g2OtherVertices = new ArrayList<Vertex>();
        for (Integer idx : secondGraphVertex2Index.inverse().keySet()) {
            if (!g2GeneralIdxSet.contains(idx)) {
                Vertex v = secondGraphVertex2Index.inverse().get(idx);
                g2OtherVertices.add(v);
                outputGraphVertices2secondOriginalGraphVertices.put(v, v);
            }
        }

        // build edges
		List<Edge> newGeneralEdges = new ArrayList<Edge>();
        g1OtherEdges = new ArrayList<Edge>();
        g2OtherEdges = new ArrayList<Edge>();
        List<Edge> newG1DeprecatedEdges = new ArrayList<Edge>();
        List<Edge> newG2DeprecatedEdges = new ArrayList<Edge>();

        for (Vertex outVertex : g1OtherVertices) {
            for (Edge e : g1.getEdges()) {
                if (newG1DeprecatedEdges.contains(e))
                    continue;

                Vertex src = e.getSource();
                Vertex trg = e.getTarget();

                if (src == null || trg == null)
                    continue;

                Vertex inVertex = null;
                if (src.equals(outVertex))
                    inVertex = trg;

                if (trg.equals(outVertex))
                    inVertex = src;

                if (inVertex != null) {
                    int idx = firstGraphVertex2Index.get(inVertex);
                    Vertex newInVertex = newG1VertexMergeMap.get(idx);

                    // add to deprecated edge list (double adding)
                    newG1DeprecatedEdges.add(e);

                    Edge outputEdge;
                    if (newInVertex != null) {
                        if (inVertex == trg)
                            outputEdge = new Edge(outVertex, newInVertex, e.getAttributes());
                        else
                            outputEdge = new Edge(newInVertex, outVertex, e.getAttributes());
                    } else {
                        if (inVertex == trg)
                            outputEdge = new Edge(outVertex, inVertex, e.getAttributes());
                        else
                            outputEdge = new Edge(inVertex, outVertex, e.getAttributes());
                    }
                    g1OtherEdges.add(outputEdge);
                }
            }
        }

        for (Vertex outVertex : g2OtherVertices) {
            for (Edge e : g2.getEdges()) {
                if (newG2DeprecatedEdges.contains(e))
                    continue;

                Vertex src = e.getSource();
                Vertex trg = e.getTarget();

                if (src == null || trg == null)
                    continue;

                Vertex inVertex = null;
                if (src.equals(outVertex))
                    inVertex = trg;

                if (trg.equals(outVertex))
                    inVertex = src;

                if (inVertex != null) {
                    int idx = secondGraphVertex2Index.get(inVertex);
                    Vertex newInVertex = newG2VertexMergeMap.get(idx);

                    // add to deprecated edge list (double adding)
                    newG2DeprecatedEdges.add(e);

                    Edge outputEdge;
                    if (newInVertex != null) {
                        if (inVertex == trg)
                            outputEdge = new Edge(outVertex, newInVertex, e.getAttributes());
                        else
                            outputEdge = new Edge(newInVertex, outVertex, e.getAttributes());
                    } else {
                        if (inVertex == trg)
                            outputEdge = new Edge(outVertex, inVertex, e.getAttributes());
                        else
                            outputEdge = new Edge(inVertex, outVertex, e.getAttributes());
                    }
                    g2OtherEdges.add(outputEdge);
                }
            }
        }

        // build general edges
        for (int i = 0; i < edges.length; i++) {
			for (int j = i + 1; j < edges.length; j++) {
				BiGraphEdge mcs_v1 = edges[i];
				BiGraphEdge mcs_v2 = edges[j];

				int g1Idx1 = mcs_v1.getSrc();
				int g1Idx2 = mcs_v2.getSrc();
				int g2Idx1 = mcs_v1.getDst();
				int g2Idx2 = mcs_v2.getDst();

                // edges from v1 to v2
                MergingEdgesResult mergingEdgesResultTo = mergingEdges(mcs_v1, mcs_v2, newVertexMergeTable[g1Idx1][g2Idx1], newVertexMergeTable[g1Idx2][g2Idx2]);
				for (Edge e : mergingEdgesResultTo.generalEdgesMoreBarrier) {
                    newGeneralEdges.add(e);
                }

                for (Edge e : mergingEdgesResultTo.otherG1Edges) {
                    int idx1 = firstGraphVertex2Index.get(e.getSource());
                    int idx2 = firstGraphVertex2Index.get(e.getTarget());
                    Vertex newSrcVertex = newG1VertexMergeMap.get(idx1);
                    Vertex newTrgVertex = newG1VertexMergeMap.get(idx2);
                    g1OtherEdges.add(new Edge(newSrcVertex,  newTrgVertex, e.getAttributes()));
                }

                for (Edge e : mergingEdgesResultTo.otherG2Edges) {
                    int idx1 = secondGraphVertex2Index.get(e.getSource());
                    int idx2 = secondGraphVertex2Index.get(e.getTarget());
                    Vertex newSrcVertex = newG2VertexMergeMap.get(idx1);
                    Vertex newTrgVertex = newG2VertexMergeMap.get(idx2);
                    g2OtherEdges.add(new Edge(newSrcVertex,  newTrgVertex, e.getAttributes()));
                }

                // edges from v2 to v1
                MergingEdgesResult mergingEdgesResultFrom = mergingEdges(mcs_v2, mcs_v1, newVertexMergeTable[g1Idx2][g2Idx2], newVertexMergeTable[g1Idx1][g2Idx1]);
                for (Edge e : mergingEdgesResultFrom.generalEdgesMoreBarrier) {
                    newGeneralEdges.add(e);
                }

                for (Edge e : mergingEdgesResultFrom.otherG1Edges) {
                    int idx1 = firstGraphVertex2Index.get(e.getSource());
                    int idx2 = firstGraphVertex2Index.get(e.getTarget());
                    Vertex newSrcVertex = newG1VertexMergeMap.get(idx1);
                    Vertex newTrgVertex = newG1VertexMergeMap.get(idx2);
                    g1OtherEdges.add(new Edge(newSrcVertex,  newTrgVertex, e.getAttributes()));
                }

                for (Edge e : mergingEdgesResultFrom.otherG2Edges) {
                    int idx1 = secondGraphVertex2Index.get(e.getSource());
                    int idx2 = secondGraphVertex2Index.get(e.getTarget());
                    Vertex newSrcVertex = newG2VertexMergeMap.get(idx1);
                    Vertex newTrgVertex = newG2VertexMergeMap.get(idx2);
                    g2OtherEdges.add(new Edge(newSrcVertex,  newTrgVertex, e.getAttributes()));
                }
            }
		}
		
		// build graph
        List<Vertex> newVertices = new ArrayList<Vertex>();
        newVertices.addAll(newGeneralVertices);
        newVertices.addAll(g1OtherVertices);
        newVertices.addAll(g2OtherVertices);

        List<Edge> newEdges = new ArrayList<Edge>();
        newEdges.addAll(newGeneralEdges);
        newEdges.addAll(g1OtherEdges);
        newEdges.addAll(g2OtherEdges);

        return new Graph(newVertices, newEdges, g1.isDirected() | g2.isDirected());
	}

    private float getVertexSimilarityPercentage4Solution(Solution solution) {
        if (solution == null || solution.getEdges() == null || solution.getEdges().length == 0)
            return 0;

        BiGraphEdge[] edges = solution.getEdges();

        // build vertices
        float vertex_result = 0;
        Vertex[][] new_vertex_table = new Vertex[g1.getVertexCount()][g2.getVertexCount()];
        List<Vertex> new_vertices = new ArrayList<Vertex>();
        for (int i = 0; i < edges.length; i++) {
            int idx1 = edges[i].getSrc();
            int idx2 = edges[i].getDst();
            Vertex v1 = firstGraphVertex2Index.inverse().get(idx1);
            Vertex v2 = secondGraphVertex2Index.inverse().get(idx2);
            Vertex v = new Vertex(mergingAttributeItems(v1, v2));
            vertex_result += vertexMatchingTable[idx1][idx2];
            new_vertex_table[idx1][idx2] = v;
            new_vertices.add(v);
        }

        return vertex_result;
    }
	
	private float getEdgeSimilarityPercentage4Solution(Solution solution) {
		if (solution == null || solution.getEdges() == null || solution.getEdges().length == 0)
            return 0;

		BiGraphEdge[] edges = solution.getEdges();

		// build vertices
		float vertex_result = 0;
		Vertex[][] new_vertex_table = new Vertex[g1.getVertexCount()][g2.getVertexCount()];
		List<Vertex> new_vertices = new ArrayList<Vertex>();
		for (int i = 0; i < edges.length; i++) {
			int idx1 = edges[i].getSrc();
			int idx2 = edges[i].getDst();
			Vertex v1 = firstGraphVertex2Index.inverse().get(idx1);
			Vertex v2 = secondGraphVertex2Index.inverse().get(idx2);
			Vertex v = new Vertex(mergingAttributeItems(v1, v2));
			vertex_result += vertexMatchingTable[idx1][idx2];
			new_vertex_table[idx1][idx2] = v;
			new_vertices.add(v);
		}

		// build edges
		float edge_result = 0;
		List<Edge> new_edges = new ArrayList<Edge>();
		for (int i = 0; i < edges.length; i++) {
			for (int j = i + 1; j < edges.length; j++) {
				BiGraphEdge mcs_v1 = edges[i];
				BiGraphEdge mcs_v2 = edges[j];
				int g1Idx1 = mcs_v1.getSrc();
				int g1Idx2 = mcs_v2.getSrc();
				int g2Idx1 = mcs_v1.getDst();
				int g2Idx2 = mcs_v2.getDst();

                MergingEdgesResult mergingEdgesResultTo = mergingEdges(mcs_v1, mcs_v2, new_vertex_table[g1Idx1][g2Idx1], new_vertex_table[g1Idx2][g2Idx2]);
				new_edges.addAll(mergingEdgesResultTo.allGeneralEdges.keySet());
				for (Float ratio : mergingEdgesResultTo.allGeneralEdges.values())
					edge_result += ratio;

                MergingEdgesResult mergingEdgesResultFrom = mergingEdges(mcs_v2, mcs_v1, new_vertex_table[g1Idx2][g2Idx2], new_vertex_table[g1Idx1][g2Idx1]);
				new_edges.addAll(mergingEdgesResultFrom.allGeneralEdges.keySet());
				for (Float ratio : mergingEdgesResultFrom.allGeneralEdges.values())
					edge_result += ratio;
			}
		}
		
		// build graph
        return edge_result;
	}

	private Solution matching(SolutionSet solutionSet, IGraphComparisonAlgorithmObserver observer) {
        BigDecimal lostCases = new BigDecimal(0);
        int loop = 0;

        Solution bestSolution = new Solution(new BiGraphEdge[0]);
        float bestVertexRatio = 0;
        float bestEdgeRatio = 0;
        while (!stopAnyPhase.get()) {
            Solution solution = solutionSet.next();

            if (solution == null)
                break;

            //VGMainService.logger.printDebug("solution : " + solution.toString());

            float vertexRatio = getVertexSimilarityPercentage4Solution(solution);

            int compResult = Float.compare(vertexRatio, bestVertexRatio);
            if (compResult > 0) {
                bestVertexRatio = vertexRatio;
                bestEdgeRatio = getEdgeSimilarityPercentage4Solution(solution);
                bestSolution = solution;

                //VGMainService.logger.printDebug("best vertex ratio = " + bestVertexRatio);
                //VGMainService.logger.printDebug("best edge ratio = " + bestEdgeRatio);
            } else if (compResult == 0) {
                float edgeRatio = getEdgeSimilarityPercentage4Solution(solution);
                if (Float.compare(edgeRatio, bestEdgeRatio) > 0) {
                    bestEdgeRatio = edgeRatio;
                    bestSolution = solution;

                    //VGMainService.logger.printDebug("best edge ratio = " + bestEdgeRatio);
                }
            }

            loop++;
            if (loop >= 100) {
                lostCases = lostCases.add(new BigDecimal(loop));
                if (observer != null)
                    observer.update4phase3(lostCases, solutionSet.upperBoundCountCases());
                loop = 0;
            }
        }

        lostCases = lostCases.add(new BigDecimal(loop));
        if (observer != null)
            observer.update4phase3(lostCases, lostCases);

        // reset stopCalculation field
        stopAnyPhase.set(false);

        // Print best solution
        if (bestSolution == null)
            VGMainServiceHelper.logger.printDebug("Graph comparison, best solution = null");
        else
            VGMainServiceHelper.logger.printDebug("Graph comparison, Best solution = " + bestSolution.toString());

        VGMainServiceHelper.logger.printDebug("Graph comparison, Count cases = " + lostCases);

		return bestSolution;
	}

    /**
     * Build vertex matching table.
     */
	private float[][] buildVertexMatchingTable() {
        // build vertex matching table
        float[][] vertexMatchingTable = new float[g1.getVertexCount()][g2.getVertexCount()];

		for (Vertex v1 : g1.getVertices()) {
			for(Vertex v2 : g2.getVertices()) {
				int idx1 = firstGraphVertex2Index.get(v1);
				int idx2 = secondGraphVertex2Index.get(v2);
				vertexMatchingTable[idx1][idx2] = getSimilarityPercentage(v1, v2);
			}
		}

        return vertexMatchingTable;
	}

    /**
     * Build edge matching table.
     */
	private float[][] buildEdgeMatchingTable() {
        float[][] edgeMatchingTable = new float[g1.getEdgeCount()][g2.getEdgeCount()];

		for (Edge e1 : g1.getEdges()) {
			for(Edge e2 : g2.getEdges()) {
				int idx1 = firstGraphEdge2Index.get(e1);
				int idx2 = secondGraphEdge2Index.get(e2);
				edgeMatchingTable[idx1][idx2] = getSimilarityPercentage(e1, e2);
			}
		}

        return edgeMatchingTable;
	}

    /**
     * Method for initializing main data.
     */
	private void init() {
        // initialize main data
        vertexBarrier = 1.0f;
        edgeBarrier = 1.0f;

        firstGraphVertex2Index = GraphUtils.orderVertices(g1);
        secondGraphVertex2Index = GraphUtils.orderVertices(g2);

        firstGraphEdge2Index = GraphUtils.orderEdges(g1);
        secondGraphEdge2Index = GraphUtils.orderEdges(g2);

		g1Vertices = new AttributeItem[g1.getVertexCount()];
        g2Vertices = new AttributeItem[g2.getVertexCount()];

        g1Edges = new AttributeItem[g1.getEdgeCount()];
        g2Edges = new AttributeItem[g2.getEdgeCount()];

        g1Vertices = initVertices(g1, firstGraphVertex2Index);
        g2Vertices = initVertices(g2, secondGraphVertex2Index);

        g1Edges = initEdges(g1, firstGraphEdge2Index);
        g2Edges = initEdges(g2, secondGraphEdge2Index);

        unitedVertices = HashBiMap.create();
        separatedVertices = HashBiMap.create();

        // initialize vertex & edge attribute to weight map
        vertexAttribute2Weight = new HashMap<String, Float>();
        edgeAttribute2Weight = new HashMap<String, Float>();

        vertexAttribute2Weight.put(INCOMING_COUNT_EDGE, MAX_PERCENT_VALUE);
        edgeAttribute2Weight.put(OUTGOING_COUNT_EDGE, MAX_PERCENT_VALUE);

        collectVertexAttributes(g1, vertexAttribute2Weight);
        collectVertexAttributes(g2, vertexAttribute2Weight);

        collectEdgeAttributes(g1, edgeAttribute2Weight);
        collectEdgeAttributes(g2, edgeAttribute2Weight);

        calculateWeightRatio();
    }

    private void calculateWeightRatio() {
        vertexAttribute2WeightRatio = new HashMap<String, Float>();
        edgeAttribute2WeightRatio = new HashMap<String, Float>();

        float vertexWeight = 0.0f;
        for (Float weight : vertexAttribute2Weight.values()) {
            vertexWeight += weight;
        }

        float edgeWeight = 0.0f;
        for (Float weight : edgeAttribute2Weight.values()) {
            edgeWeight += weight;
        }

        for (String attrName : vertexAttribute2Weight.keySet()) {
            float weight = vertexAttribute2Weight.get(attrName);
            vertexAttribute2WeightRatio.put(attrName, weight / vertexWeight);
        }

        for (String attrName : edgeAttribute2Weight.keySet()) {
            float weight = edgeAttribute2Weight.get(attrName);
            edgeAttribute2WeightRatio.put(attrName, weight / edgeWeight);
        }
    }

    /**
     * Returns percentage of similarity of two vertices in range from 0 to 1.
     */
    private float getSimilarityPercentage(Vertex g1vertex, Vertex g2vertex) {
        int g1VertexIdx = firstGraphVertex2Index.get(g1vertex);
        int g2VertexIdx = secondGraphVertex2Index.get(g2vertex);

        AttributeItem g1VertexAttributeItem = g1Vertices[g1VertexIdx];
        AttributeItem g2VertexAttributeItem = g2Vertices[g2VertexIdx];

        float result = MAX_PERCENT_VALUE;

        for (String attrName : vertexAttribute2WeightRatio.keySet()) {
            float match = 1.0f;
            Attribute g1Attribute = g1VertexAttributeItem.getAttribute(attrName);
            Attribute g2Attribute = g2VertexAttributeItem.getAttribute(attrName);
            if (g1Attribute != null && g2Attribute != null) {
                if (g1Attribute.isRealType() && g2Attribute.isRealType()) {
                    if (enableStrongComparison)
                        match = strongDoubleComparison(g1Attribute.getRealValue(), g2Attribute.getRealValue());
                    else
                        match = flexibleDoubleComparison(g1Attribute.getRealValue(), g2Attribute.getRealValue());
                } else if (g1Attribute.isStringType() && g2Attribute.isStringType()) {
                    if (enableStrongComparison)
                        match = strongStringComparison(g1Attribute.getStringValue(), g2Attribute.getStringValue());
                    else
                        match = flexibleStringComparison(g1Attribute.getStringValue(), g2Attribute.getStringValue());
                } else {
                    match = 0.0f;
                }
            } else if ((g1Attribute == null && g2Attribute != null) || (g1Attribute != null && g2Attribute == null)) {
                match = 0.0f;
            }
            result -= ((1 - match) * vertexAttribute2WeightRatio.get(attrName));
        }

		return result;
	}

    /**
     * Returns percentage of similarity of two edges in range from 0 to 1.
     */
	private float getSimilarityPercentage(Edge g1Edge, Edge g2Edge) {
        int g1EdgeIdx = firstGraphEdge2Index.get(g1Edge);
        int g2EdgeIdx = secondGraphEdge2Index.get(g2Edge);

        AttributeItem g1EdgeAttributeItem = g1Edges[g1EdgeIdx];
        AttributeItem g2EdgeAttributeItem = g2Edges[g2EdgeIdx];

        float result = MAX_PERCENT_VALUE;

        for (String attrName : edgeAttribute2WeightRatio.keySet()) {
            float match = 1.0f;
            Attribute g1Attribute = g1EdgeAttributeItem.getAttribute(attrName);
            Attribute g2Attribute = g2EdgeAttributeItem.getAttribute(attrName);
            if (g1Attribute != null && g2Attribute != null) {
                if (g1Attribute.isRealType() && g2Attribute.isRealType()) {
                    if (enableStrongComparison)
                        match = strongDoubleComparison(g1Attribute.getRealValue(), g2Attribute.getRealValue());
                    else
                        match = flexibleDoubleComparison(g1Attribute.getRealValue(), g2Attribute.getRealValue());
                } else if (g1Attribute.isStringType() && g2Attribute.isStringType()) {
                    if (enableStrongComparison)
                        match = strongStringComparison(g1Attribute.getStringValue(), g2Attribute.getStringValue());
                    else
                        match = flexibleStringComparison(g1Attribute.getStringValue(), g2Attribute.getStringValue());
                } else {
                    match = 0.0f;
                }
            } else if ((g1Attribute == null && g2Attribute != null) || (g1Attribute != null && g2Attribute == null)) {
                match = 0.0f;
            }
            result -= ((1 - match) * edgeAttribute2WeightRatio.get(attrName));
        }

        return result;
	}

	private AttributeItem mergingAttributeItems(AttributeItem item1, AttributeItem item2) {
		List<Attribute> attributes = new ArrayList<Attribute>();
		for (Attribute attr1 : item1.getAttributes()) {
			Attribute attr2 = item2.getAttribute(attr1.getName());
            String htmlDiff;
            if (attr2 != null) {
                String value1 = attr1.toNotNullStringValue();
                String value2 = attr2.toNotNullStringValue();
                if (value1 == null || value2 == null) {
                    htmlDiff = "<font color=\"green\">" + value1 + "</font>" + "<b>|</b>" + "<font color=\"red\">" + value2 + "</font>";
                } else {
                    if (value1.equals(value2)) {
                        htmlDiff = "<font color=\"green\">" + value1 + "</font>" + "<b>|</b>" + "<font color=\"green\">" + value2 + "</font>";
                    } else {
                        htmlDiff = "<font color=\"green\">" + value1 + "</font>" + "<b>|</b>" + "<font color=\"red\">" + value2 + "</font>";
                    }
                }
			} else {
                htmlDiff = "<font color=\"green\">" + attr1.toNotNullStringValue() + "</font>" + "<b>|</b>" + "<font color=\"red\">" + "null" + "</font>";
			}
            attributes.add(new Attribute(attr1.getName(), htmlDiff, AttributeHeader.STRING_ATTRIBUTE_TYPE));
        }
		return new AttributeItem(attributes);
	}
	
	/**
	 * Returns shared edges between v1 and v2.
	 */
	private MergingEdgesResult mergingEdges(BiGraphEdge v1, BiGraphEdge v2, Vertex new_v1, Vertex new_v2) {
		Map<Edge, Float> allGeneralEdges = new HashMap<Edge, Float>();
        List<Edge> generalEdgesMoreBarrier = new ArrayList<Edge>();
        List<Edge> generalEdgesLowBarrier = new ArrayList<Edge>();

		int g1Idx1 = v1.getSrc();
		int g1Idx2 = v2.getSrc();
		int g2Idx1 = v1.getDst();
		int g2Idx2 = v2.getDst();
		
		Vertex g1v1 = firstGraphVertex2Index.inverse().get(g1Idx1);
		Vertex g1v2 = firstGraphVertex2Index.inverse().get(g1Idx2);
		Vertex g2v1 = secondGraphVertex2Index.inverse().get(g2Idx1);
		Vertex g2v2 = secondGraphVertex2Index.inverse().get(g2Idx2);
		
		List<Edge> otherG1Edges = new ArrayList<Edge>();
		for (Edge e : g1.getEdges()) {
			Vertex src = e.getSource(), trg = e.getTarget();
			
			if (src == null || trg == null) continue;
			
			if (src.equals(g1v1) && trg.equals(g1v2)) {
				otherG1Edges.add(e);
			}
		}

		List<Edge> otherG2Edges = new ArrayList<Edge>();
		for (Edge e : g2.getEdges()) {
			Vertex src = e.getSource(), trg = e.getTarget();
			
			if (src == null || trg == null) continue;
			
			if (src.equals(g2v1) && trg.equals(g2v2)) {
				otherG2Edges.add(e);
			}
		}
		
		// merging
		if (otherG1Edges.size() > 0 && otherG2Edges.size() > 0) {
			float[][] table = new float[otherG1Edges.size()][otherG2Edges.size()];
			int i = 0, j = 0;
			for (Edge e1 : otherG1Edges) {
				for (Edge e2 : otherG2Edges) {
					int idx1 = firstGraphEdge2Index.get(e1);
					int idx2 = secondGraphEdge2Index.get(e2);
					table[i][j] = edgeMatchingTable[idx1][idx2];
					j++;
				}
				i++;
			}
			
			HungarianAlgorithmOutput hungarianAlgorithmOutput = new HungarianAlgorithm(table, HungarianAlgorithm.MAXIMIZE).execute();
            int[] assignment = hungarianAlgorithmOutput.getAssigned();
			
			for (i = 0; i < assignment.length; i++) {
				if (assignment[i] < 0)
                    continue;

                Edge e1 = otherG1Edges.get(i);
				Edge e2 = otherG2Edges.get(assignment[i]);
				int idx1 = firstGraphEdge2Index.get(e1);
				int idx2 = secondGraphEdge2Index.get(e2);
				float ratio = edgeMatchingTable[idx1][idx2];

                Edge generalEdge = new Edge(new_v1, new_v2, mergingAttributeItems(e1, e2));
                allGeneralEdges.put(generalEdge, ratio);
                if (ratio >= edgeBarrier) {
                    otherG1Edges.remove(e1);
                    otherG2Edges.remove(e2);
                    generalEdgesMoreBarrier.add(generalEdge);
                } else {
                    generalEdgesLowBarrier.add(generalEdge);
                }
			}
		}
		
		return new MergingEdgesResult(allGeneralEdges, generalEdgesMoreBarrier, generalEdgesLowBarrier, otherG1Edges, otherG2Edges);
	}

//==============================================================================
//-----------------STATIC METHODS-----------------------------------------------
    // Returns result in range from 0 to 1
    private static float flexibleDoubleComparison(double value1, double value2) {
        if (value1 < 0 && value2 < 0) {
            value1 = -value1;
            value2 = -value2;
        }

        if (value1 < 0 && value2 > 0) {
            value1 = -value1;
            value2 = value1 + value2;
        }

        if (value2 < 0 && value1 > 0) {
            value2 = - value2;
            value1 = value1 + value2;
        }

        // not zero
        value1++;
        value2++;


        float diff;
        if (value1 > value2)
            diff = (float)(value2 / value1);
        else
            diff = (float)(value1 / value2);

        if (diff > 1) diff = 1;
        if (diff < 0) diff = 0;

        return  diff;
    }

    // Returns result in range from 0 to 1
    private static float flexibleStringComparison(String value1, String value2) {
        float diff = 0;

        if (value1 == null || value2 == null)
            return diff;

        byte[] bytes2 = value2.getBytes();
        int i = 0;
        for (byte b : value1.getBytes()) {
            if (bytes2.length <= i || b != bytes2[i]) {
                break;
            } else {
                i++;
            }
        }
        diff = (2 * i) / (float)(value1.length() + value2.length());

        if (diff > 1) diff = 1;
        if (diff < 0) diff = 0;

        return  diff;
    }

    // Returns result which equals 0 or 1.
    private static float strongDoubleComparison(double value1, double value2) {
        if (Double.compare(value1, value2) == 0)
            return 1.0f;
        return 0.0f;
    }

    // Returns result which equals 0 or 1.
    private static float strongStringComparison(String value1, String value2) {
        if ((value1 == null && value2 == null) || (value1 != null && value2 != null && value1.equals(value2)))
            return 1.0f;

        return 0.0f;
    }

    private static AttributeItem[] initVertices(Graph graph, BiMap<Vertex, Integer> vertex2index) {
        AttributeItem[] vertices = new AttributeItem[0];

        if (graph == null)
            return vertices;

        vertices = new AttributeItem[graph.getVertexCount()];
        for (Vertex v : graph.getVertices()) {
            vertices[vertex2index.get(v)] = new AttributeItem(v);
        }

        int[] incoming = new int[graph.getVertexCount()];
        int[] outgoing = new int[graph.getVertexCount()];

        for (Edge e : graph.getEdges()) {
            if (graph.isDirected()) {
                outgoing[vertex2index.get(e.getSource())]++;
                incoming[vertex2index.get(e.getTarget())]++;
            } else {
                outgoing[vertex2index.get(e.getSource())]++;
                outgoing[vertex2index.get(e.getTarget())]++;
                incoming[vertex2index.get(e.getSource())]++;
                incoming[vertex2index.get(e.getTarget())]++;
            }
        }

        // save in and out to vertices
        for (int i = 0; i < vertices.length; i++) {
            vertices[i].addIntAttribute(INCOMING_COUNT_EDGE, incoming[i]);
            vertices[i].addIntAttribute(OUTGOING_COUNT_EDGE, outgoing[i]);
        }

        return vertices;
    }

    private static AttributeItem[] initEdges(Graph graph, BiMap<Edge, Integer> edge2index) {
        AttributeItem[] edges = new AttributeItem[0];

        if (graph == null)
            return edges;

        edges = new AttributeItem[graph.getEdgeCount()];
        for (Edge e : graph.getEdges()) {
            edges[edge2index.get(e)] = new AttributeItem(e);
        }

        return edges;
    }

    /**
     * Adds attributes to map, if this map hasn't contains it.
     * @param vertexAttribute2Weight - result map.
     */
    private static void collectVertexAttributes(Graph graph, Map<String, Float> vertexAttribute2Weight) {
        if (graph == null)
            return;

        for (Vertex v : graph.getVertices()) {
            for (Attribute a : v.getAttributes()) {
                String name = a.getName();
                if (name != null) {
                    vertexAttribute2Weight.put(name, MIDDLE_PERCENT_VALUE);
                }
            }
        }
    }

    /**
     * Adds attributes to map, if this map hasn't contains it.
     * @param edgeAttribute2Weight - result map.
     */
    private static void collectEdgeAttributes(Graph graph, Map<String, Float> edgeAttribute2Weight) {
        if (graph == null)
            return;

        for (Edge v : graph.getEdges()) {
            for (Attribute a : v.getAttributes()) {
                String name = a.getName();
                if (name != null) {
                    edgeAttribute2Weight.put(name, MIDDLE_PERCENT_VALUE);
                }
            }
        }
    }

    private static void normalise(float[][] array) {
        if (array == null)
            return;

        float max = 0;
        for (float[] row : array) {
            for (float col : row) {
                if (max < col)
                    max = col;
            }
        }

        if (max == 0)
            max = 1.0f;

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                array[i][j] /= max;
            }
        }
    }

//==============================================================================
//-----------------STATIC INNER CLASSES-----------------------------------------
    private static class MergingEdgesResult {
        public Map<Edge, Float> allGeneralEdges;
        public List<Edge> generalEdgesMoreBarrier;
        public List<Edge> generalEdgesLowBarrier;
        public List<Edge> otherG1Edges;
        public List<Edge> otherG2Edges;

        private MergingEdgesResult(Map<Edge, Float> allGeneralEdges, List<Edge> generalEdgesMoreBarrier, List<Edge> generalEdgesLowBarrier, List<Edge> otherG1Edges, List<Edge> otherG2Edges) {
            this.allGeneralEdges = allGeneralEdges;
            this.generalEdgesMoreBarrier = generalEdgesMoreBarrier;
            this.generalEdgesLowBarrier = generalEdgesLowBarrier;
            this.otherG1Edges = otherG1Edges;
            this.otherG2Edges = otherG2Edges;
        }
    }
}
